import collections


class Solution(object):
    def isSolvable(self, words, result):
        left_dict = collections.defaultdict(int)
        right_dict = collections.defaultdict(int)
        t_set = set()
        not_zero = set()
        for word in words:
            m = len(word)
            for i in range(m):
                if i == 0 and m > 1:
                    not_zero.add(word[i])
                left_dict[word[m - 1 - i]] += 10 ** i
                t_set.add(word[m - 1 - i])
        m = len(result)
        for i in range(m):
            if i == 0 and m > 1:
                not_zero.add(result[0])
            right_dict[result[m - 1 - i]] += 10 ** i
            t_set.add(result[m - 1 - i])
        ans_dict = {}
        for key in left_dict:
            ans_dict[key] = left_dict[key]
        for key in right_dict:
            if key in ans_dict:
                ans_dict[key] -= right_dict[key]
                if ans_dict[key] == 0:
                    ans_dict.pop(key)
            else:
                ans_dict[key] = - right_dict[key]
        ans_list = [[key, ans_dict[key]] for key in ans_dict]
        ans_list.sort(key=lambda x: -abs(x[1]))
        c_list = [c[0] for c in ans_list]
        ans_list = [c[1] for c in ans_list]
        m = len(ans_list)
        zheng_list = [0] * m
        fu_list = [0] * m
        zheng_list[-1] += max(ans_list[-1], 0)
        fu_list[-1] += min(ans_list[-1], 0)
        for i in range(m - 2, -1, -1):
            zheng_list[i] += zheng_list[i + 1] + max(ans_list[i + 1], 0)
            fu_list[i] += fu_list[i + 1] + min(ans_list[i + 1], 0)

        def dfs(i, ans, val):
            if i == m:
                if ans == 0:
                    return True
                else:
                    return False
            if c_list[i] in not_zero:
                min_val = 1
            else:
                min_val = 0
            if ans_list[i] > 0:
                for j in range(min_val, 10):
                    if (val >> j) & 1 == 0:
                        if ans_list[i] * j + ans + 9 * fu_list[i] <= 0:
                            next_ans = ans + ans_list[i] * j
                            next_val = val | (1 << j)
                            if dfs(i + 1, next_ans, next_val):
                                return True
                        else:
                            break
            else:
                for j in range(min_val, 10):
                    if (val >> j) & 1 == 0:
                        if ans_list[i] * j + ans + 9 * zheng_list[i] >= 0:
                            next_ans = ans + ans_list[i] * j
                            next_val = val | (1 << j)
                            if dfs(i + 1, next_ans, next_val):
                                return True
                        else:
                            break
            return False
        return dfs(0, 0, 0)


data = Solution()
# words = ["SEND", "MORE"]
# result = "MONEY"
# print(data.isSolvable(words, result))
# words = ["LEET", "CODE"]
# result = "POINT"
# print(data.isSolvable(words, result))
words = ["CBA", "CBA", "CBA", "CBA", "CBA"]
result = "EDD"
print(data.isSolvable(words, result))
